home *** CD-ROM | disk | FTP | other *** search
/ ftp.cs.arizona.edu / ftp.cs.arizona.edu.tar / ftp.cs.arizona.edu / icon / newsgrp / group93c.txt / 000003_icon-group-sender _Wed Jun 30 17:07:59 1993.msg < prev    next >
Internet Message Format  |  1994-02-02  |  3KB
  1. Received: from owl.CS.Arizona.EDU by cheltenham.CS.Arizona.EDU; Wed, 30 Jun 1993 18:03:29 MST
  2. Received: by owl.cs.arizona.edu; Wed, 30 Jun 1993 18:03:28 MST
  3. Date: Wed, 30 Jun 93 17:07:59 -0700
  4. From: wgg@cs.ucsd.edu (William Griswold)
  5. Message-Id: <9307010007.AA04348@gremlin>
  6. To: abrahams@acm.org, icon-group@cs.arizona.edu
  7. Subject: Re:  Tables versus lists
  8. Status: R
  9. Errors-To: icon-group-errors@cs.arizona.edu
  10.  
  11. Paul,
  12.  
  13. Arrays in Icon are allocated in segments that double the size of the
  14. array, so that look ups are on average logarithmic in time for random
  15. access.  The logarithmic behavior does not show up until arrays are
  16. rather large.  Array elements are generated in constant time.
  17.  
  18. Table elements are generated in basically constant time up to a certain
  19. size, whereafter you will see a linear degradation.  The degradation
  20. point depends on the implementation, but it is rarely a concern for
  21. the programmer.
  22.  
  23. I would use arrays and switch later if necessary.  Since their syntax
  24. is very similar for most operations, making the change should not be
  25. difficult.  If it would be, you could encapsulate the syntax of the
  26. data structure accesses with procedures.
  27.  
  28. In fact, you don't need to know the implementation in most cases:
  29. a simple statement of the computational complexity of key operations
  30. is sufficient.
  31.  
  32.                         Bill Griswold
  33.                         UCSD
  34.  
  35.  
  36. >From: Paul_Abrahams@MTS.cc.Wayne.edu
  37. >
  38. >Suppose that I have a "growing array" whose elements I frequently
  39. >reference.  I can implement that array in Icon in either of two ways: as
  40. >a list or as a table.  The construct for referencing an array element is
  41. >the same in either case:  array[n].  The constructs for adding an element
  42. >are different, but not that different:
  43. >  push(array, element)
  44. >versus
  45. >  array[integer(*array+1)] := element
  46. > 
  47. >My question is: how do the efficiencies of these constructs compare?  I
  48. >know that lists are implemented efficiently if allocated all at once, but
  49. >how about the case where they grow an element at a time?  If finding an
  50. >element requires a search down a linked list with hundreds of items, the
  51. >table is clearly preferable; but if finding an element in the list can be
  52. >done with an integer-indexed lookup, the list is clearly preferable.
  53. > 
  54. >This is a good example of a choice in Icon that is difficult to make
  55. >intelligently without a knowledge of the implementation and that can make
  56. >a great difference in performance.
  57. > 
  58. >Paul Abrahams
  59. >Reply-To: abrahams@acm.org
  60.